package two.chapter_1.c1_3;

import edu.princeton.cs.algs4.StdRandom;

import java.util.Iterator;

/**
 * 随机背包：所谓随机背包就是迭代时能够随机访问背包中的所有元素
 * @param <Item>
 */
public class RandomBag<Item> implements Collection<Item> {
    private Item [] items;
    private static final int DEFAULT_SIZE=10;
    private int size;
    public RandomBag(){
        items= (Item[]) new Object[DEFAULT_SIZE];
    }

    public void add(Item item){
        ensureCapacity(size+1);

        items[size]=item;
        size++;
    }

    private void ensureCapacity(int length) {
        if (length>items.length){
            //需要扩容
            int newLenght=items.length*2;
            Item [] newItems= (Item[]) new Object[newLenght];
            System.arraycopy(items,0,newItems,0,items.length);

            items=newItems;
        }
    }

    @Override
    public boolean isEmpty() {
        return size()==0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public Iterator<Item> iterator() {
        return new Iter();
    }

    private class Iter implements Iterator<Item>{

        private int index;
        public Iter(){
            StdRandom.shuffle(items);
        }
        @Override
        public boolean hasNext() {
            return index<size;
        }

        @Override
        public Item next() {
            Item item=items[index];
            index++;
            return item;
        }

        @Override
        public void remove() {

        }
    }
}
